package com.ruijixiang.leetcode.weekly.leetcode2024.leetcode20241020;

public class Leetcode3326 {

    /**
     * 使数组非递减的最少除法操作次数：预处理+从右到左贪心
     * @param nums
     * @return
     */
    private static final int MX=1000001;
    private static final int[] lpf=new int[MX];

    static{
        for(int i=2;i<MX;i++){
            if(lpf[i]==0){
                for(int j=i;j<MX;j+=i){
                    if(lpf[j]==0){
                        lpf[j]=i;
                    }
                }
            }
        }
    }

    public int minOperations(int[] nums){
        int ans=0;
        for(int i=nums.length-2;i>=0;i--){
            if(nums[i]>nums[i+1]){
                nums[i]=lpf[nums[i]];
                if(nums[i]>nums[i+1]){
                    return -1;
                }
                ans++;
            }
        }
        return ans;
    }
}
